\newcommand{\Srcs}{{\cal S}}
\newcommand{\Snks}{{\cal T}}
\newcommand{\expandedG}[1]{\widehat{G}[#1]}
\newcommand{\Sources}[1]{\overline{S}_{#1}}
\subsection{$O((n+k)\log^2 n)$-round offline schedule}
\label{sec:multiport}
In this section, we present an algorithm for computing an $O((n+k)
\log^2 n)$ round offline schedule.  Our bound is tight to within an
$O(\log^2 n)$ factor since the dissemination of any $k$ tokens to even
a single node of the network requires $\Omega(n + k)$ rounds in the
worst case.  We begin by defining the notion of an evolution graph
that facilitates the design of the offline algorithms.

\smallskip
\noindent
{\em Evolution graph}: Let $V$ be the set of nodes. Consider a dynamic
network of $l$ rounds numbered $1$ through $l$ and let $G_i$ be the
communication graph for round $i$. The evolution graph $\expandedG{l}$
for this network is a directed capacitated graph $G$ with $l+1$ levels
constructed as follows. We create $l+1$ copies of $V$ and call them
$V_0, V_1, V_2, \dots, V_{l}$. $V_i$ is the set of nodes at level $i$
and for each node $v$ in $V$, we call its copy in $V_i$ as $v_i$. For
$i = 1, \ldots, l$, level $i-1$ corresponds to the beginning of round
$i$ and level $i$ corresponds to the end of round $i$. Level $0$
corresponds to the network at the start.  There are two kinds of edges
in the graph.  First, for every node $v$ in $V$ and every round $i$,
we place an edge with infinite capacity from $v_{i-1}$ to $v_{i}$. We
call these edges {\em buffer edges} as they ensure tokens can be
stored at a node from the end of one round to the end of the next.
Second, for every round $i$ and every edge $(u,v) \in G_i$, we place
two directed edges with unit capacity each, one from $u_{i-1}$ to
$v_{i}$ and another from $v_{i-1}$ to $u_{i}$.  We call these edges
as {\em transmit edges} as they correspond to every node transmitting
a message to a neighbor in round $i$; the unit capacity ensures that
in a given round a node can transmit at most one token to each
neighbor.  Figure~\ref{fig:evolution} illustrates our construction.
\iflong
Lemma~\ref{lem:maxflow} explains the usefulness of this construction.
\fi

\begin{figure*}[ht]
\begin{center}
\includegraphics[width=5in]{level.jpg}
\caption{An example of how to construct the evolution graph from a
  sequence of communication graphs.}
\label{fig:evolution}
\end{center}
\end{figure*}

\iflong
\begin{lemma}
\label{lem:maxflow}
Let $S$ be a set of source nodes, each with a subset of the $k$ tokens
and let $T$ be a subset of sink nodes.  Let $\expandedG{\ell}$ be an
evolution graph over $\ell$ rounds.  Let $P$ denote a set of
edge-disjoint paths starting from $S$ and ending at $T$.  If $P$
contains for each sink $v$ and each token $i$, a distinct path from a
source containing $i$ to $v$, then $P$ yields an $\ell$-round schedule
for disseminating the $k$ tokens to each node in $T$.
\end{lemma}
\begin{proof}
For each sink $v$, let $p_v^i$ denote the path in $P$ starting at a
source containing token $i$ and ending at $v$.  We construct a
schedule in the following natural way: for each token $i$ and sink
$v$, $p_v^i$ is the schedule by which $i$ is sent from a source to
$v$.  In particular, if $(u_t, v_{t+1})$ is in $p_v^i$, then the node
$u$ sends token $i$ to $v$ in round $t$.

We need to show that this is a feasible schedule. First we observe
that two different paths in $P$ cannot use the same transmit edge
since each such edge has unit capacity.  Next we claim by induction
that if node $v_{j}$ is in $p_v^i$, then node $v$ has token $i$ by the
end of round $j$. For $j = 0$, it is trivial since path $p_v^i$ starts
from a source that has token $i$.  For $j > 0$, if $v_{j}$ is in
$p_v^i$, then the preceding edge is either a buffer edge
$(v_{j-1},v_{j})$ or a transmit edge $(u_{j-1},v_{j})$. In the former
case, by induction node $v$ has token $i$ after round $j-1$ itself. In
the latter case, node $u$ which had token $i$ after round $j-1$ by
induction was the neighbor of node $v$ in $G_j$ and $u$ sent token $i$
in round $j$ according to $p_v^i$, thus implying node $v$ has token
$i$ after round $j$. From the above claim, we conclude that whenever a
node is asked to transmit a token in round $j$, it has the token by
the end of round $j-1$. Thus the schedule we constructed is feasible.
Since $k$ paths terminate at each of the sinks, we conclude all the
tokens reach all of the sinks after round $\ell$.
\end{proof}

%[NEED TO ADD A FIGURE]

Lemma~\ref{lem:maxflow} provides the foundation for the following
randomized algorithm that first gathers all tokens at a random source
node and then, in $O(\log n)$ phases, disseminates these tokens to
geometrically increasing sets of nodes, until all of the nodes have
all tokens.
\fi
\begin{algorithm}[ht!]
\caption{Computing an $O((n+k)\log^2n)$-round schedule for $k$-gossip}
\label{alg:flow_based}
\begin{algorithmic}[1]
  \REQUIRE A sequence of communication graphs $G_1, G_2, \ldots$
  \ENSURE Schedule to disseminate $k$ tokens to all nodes

  \medskip

  \STATE {\bf Gather:} Send the $k$ tokens to a node $v_0$, chosen
  uniformly at random, in $n+k$ rounds. \label{alg:gather}

  \FOR{$i$ from $0$ to $\lg n$ (Phase~$i$)} %\label{alg.step:flow_based.phase_1}

  \STATE Choose a set $S_i$ of $2^i$ nodes uniformly at random from
  the collection of all $2^i$-size node sets. %\label{alg.step:random}
  
  \STATE {\bf Flow:} Send the $k$ tokens to every node in $S_i$ using
  a maximum flow in an $O((n+k)\log n)$-round evolution graph from the
  set $\{v_0\} \cup \bigcup_{j < i}S_i$ of sources to the set $S_i$ of
  sinks.  \ENDFOR
\end{algorithmic}
\end{algorithm}

\junk{
\begin{enumerate}
\item
{\bf Gather} all the $k$ tokens at a node $v_0$, chosen uniformly at
random from $V$.

\item
For $i = 0$ to $\lg n$: (Phase~$i$)
\begin{enumerate}
\item
{\bf Disseminate} all the $k$ tokens from nodes in $\{v_0\} \cup
\bigcup_{j < i}S_i$ to nodes in $S_i$.
\end{enumerate}
\end{enumerate}
}
\iflong
We first show that the gather step can be completed in $O(n + k)$ rounds.

\begin{lemma}
\label{lem:level.flow}
Let $k$ tokens be at given source nodes and $v$ be an arbitrary
node. Then, all the tokens can be gathered at $v$ in at most $n+k$
rounds.
\end{lemma}
\begin{proof}
Following Lemma~\ref{lem:maxflow}, it suffices to show that any
evolution graph $\expandedG{n+k}$ contains $k$ edge-disjoint paths,
each starting from a source node and ending at $v$.  To prove this, we
add to $\expandedG{n+k}$ a special vertex $v_{-1}$ at level $-1$ and
connect it to every source at level $0$ by an edge of capacity
1. (Multiple edges get fused with corresponding increase in capacity
if multiple tokens have the same source.) We claim that the value of
the min-cut between $v_{-1}$ and $v_{n+k}$ is at least $k$. Before
proving this, we complete the proof of the claim assuming this.  By
the max flow min cut theorem, the max flow between $v_{-1}$ and
$v_{n+k}$ is at least $k$. Since we connected $v_{-1}$ with each of
the $k$ token sources at level $0$ by a unit capacity edge, it follows
that unit flow can be routed from each of these sources at level $0$
to $v_{n+k}$ respecting the edge capacities, establishing the desired
claim.

To prove our claimed bound on the min cut, consider any cut of the
evolution graph separating $v_{-1}$ from $v_{n+k}$ and let $S$ be the
set of the cut containing $v_{-1}$. If $S$ includes no vertex from
level $0$, we are immediately done. Otherwise, observe that if $v_{j}
\in S$ for some $0 \leq j < (n+k)$ and $v_{j+1} \notin S$, then the
value of the cut is infinite as it cuts the buffer edge of infinite
capacity out of $v_{j}$. Thus we may assume that if $v_{j} \in S$,
then $v_{j+1} \in S$. Also observe that since each of the
communication graphs $G_1, \ldots, G_{n+k}$ are connected, if the
number of vertices in $S$ from level $j+1$ is no more than the number
of vertices from level $j$ and not all vertices from level $j+1$ are
in $S$, we get at least a contribution of 1 in the value of the cut
owing to a transmit edge. But since the total number of nodes is $n$
and $v_{n+k} \notin S$, there must be at least $k$ such levels, which
proves the claim.
\end{proof}

The remainder of the proof concerns the $\lg n$ phases.  We first
establish an elementary tree decomposition lemma that is critical in
showing that there is enough capacity in any $O((n + k)\log n)$-level
evolution graph to complete each phase.

\begin{lemma}
\label{lem:tree}
For any $n$-node tree $T$ and any integer $1 \le s \le n$, there
exists an edge-disjoint partition of $T$ into subtrees $T_1$, $T_2$,
\ldots such that each $T_i$ has $\Theta(s)$ nodes, every node of $T$
is in some $T_i$, and for each $i$, at most one node in $T_i$ is in
$\bigcup_{j \neq i} T_j$.
\end{lemma}
\begin{proof}
The proof is by induction on the size of $T$.  The base case $n = 1$
is trivial.  We now consider the induction step.  Arbitrarily root the
tree $T$ at a node $r$.  For any node $v$, let $T_v$ denote the
subtree rooted at node $v$; let $n_v = |T_v$.  Thus, $n_r = n$.  Let
$v$ denote an arbitrary node such that $n_v \ge s$ and for every child
$w$ of $v$, $n_w < s$.  We first consider the case $n_v \le 2s$.  By
the induction hypothesis, there exist edge-disjoint subtrees of $T -
T_v$ such that each subtree has $\Theta(s)$ edges, every node of $T -
T_v$ is in some subtree, and any two subtrees share at most one node.
Adding $T_v$ to this collection of subtrees yields the desired claim
for $T$.

We now consider the case where $n_v > 2s$.  Here we consider two
subcases.  The first subcase is where either $v$ is the root or $|T -
T_v| \ge s$.  We partition the children of $v$ into a set $X$ of
groups such that for each group $g \in X$, $s \le 1 + \sum_{w \in g}
n_w \le 2s$.  Let $T(g)$ denote the tree $\{v\} \cup \bigcup_{w \in g}
T_w$.  All of these subtrees are edge-disjoint and any pair of
subtrees share at most one node ($v$).  If $v$ is the root, then we
have established the desired property for $T$.  Otherwise, since $|T -
T_v| \ge s$, by the induction hypothesis, there exist edge-disjoint
subtrees of $T - T_v$ such that each subtree has $\Theta(s)$ edges,
every node of $T - T_v$ is in some subtree, and for any subtree, at
most one node in the subtree is in any of the other subtrees.  Adding
the trees $T(g)$ to this collection of subtrees yields the desired
claim for $T$.  

The second subcase is where $0 < |T - T_v| < s$.  In this subcase, we
make the parent of $v$ as the child of $v$ and proceed to the first
subcase, thus establishing the desired claim and completing the
induction step.
\end{proof}

The set of sources at the start of phase $i$ is $\Sources{i} = \{v_0\}
\cup \bigcup_{j < i} S_j$.  We next place a lower bound on the size of
$\Sources{i}$.

\begin{lemma}
\label{lem:sources}
For each $i$, $0 \le i \le \lg n$, $|\Sources{i}|$ is at least
$\min\{1, 2^{i-2}\}$ with probability at least $1 - 1/n^3$;
furthermore, $\Sources{i}$ is drawn uniformly at random from the
collection of all $|\Sources{i}|$-node sets.
\end{lemma}
\begin{proof}
For $i \le \lg\lg n$, we calculate the
probability, for each $v$, that there exist more than four values of
$j$ for which $S_j$ contains $v$ as at most
\[
\binom{\lg n}{5} n \frac{1}{n^5} \le \frac{1}{n^3}.
\]
Thus, the size of the given set is at least $2^i/4 = 2^{i-2}$ with
probability at least $1 - 1/n^3$.  We now consider the case $i >
\lg\lg n$.  Let $X_v$ denote the indicator variable for node $v$ to
be in the set.  Then,
\[ E[X_v] = 1 - (1 - 1/n)\prod_{0 \le j < i}(1 - 2^j/n) \ge 1 - e^{-1/n - \sum_{j < i} 2^j/n} = 1 - e^{-2^{i}/n} \ge 4\cdot 2^{i}/(7n).\]
Thus, the expected size of the set is at least $2^{i-1}$.  Now, using
a Chernoff-type argument (e.g., by using the method of bounded
differences and invoking Azuma's inequality), we obtain the size of
the set is at least $2^{i-2}$ whp.
\end{proof}

\begin{lemma}
\label{lem:double}
Let $r \le n$ be an arbitrary integer.  Let $\Srcs$ denote a set of at
least $r/4$ sources and $\Snks$ a set of $r$ sinks, each set drawn
independently and uniformly at random from $V$.  Then, with high
probability, the evolution graph $\expandedG{\ell}$ with $\ell =
\Theta((n+k)\log n)$ contains $rk$ edge-disjoint paths, each path
starting from a source and ending at a sink, and each sink having
exactly $k$ paths ending at it.
\end{lemma}
\begin{proof}
We add a super-source having edges of capacity $rk$ to each source and
a super-sink with edges of capacity $k$ from each sink.  It thus
suffices to prove that the maximum flow from the super-source to the
super-sink is at least $rk$.  For $r \le \lg n$, we invoke
Lemma~\ref{lem:level.flow} to obtain that the maximum flow is at least
$rk$.  In the remainder of this proof, we assume $r \ge \lg n$.  We
show that with high probability, the capacity of every cut is at least
$rk$.  Note that since there are an exponentially large number of cuts
to consider, it may not be sufficient to establish a high probability
bound for each cut separately.  We address this challenge by
identifying an important property that holds for $\expandedG{\ell}$
that enables the capacity bound to hold for all cuts simultaneously.

Consider graph $G_i$ with the source and sink sets $\Srcs$ and
$\Snks$.  Recall that $\Srcs$ and $\Snks$ are drawn uniformly at
random from the collection of all $|\Srcs|$-node and $|\Snks|$-node
sets, respectively, and $\Snks'$ is an arbitrary subset of $\Snks'$ of
size $r'$.  By Lemma~\ref{lem:tree} applied to a spanning tree of
$G_i$ with parameter $s = (n\log n)/r$, there exist edge-disjoint
subtrees $T_i^1$, $T_i^2$, \ldots, each having $\Theta(s)$ edges from
the spanning tree, and together containing all of the nodes in $V$.
Furthermore, for each $T_i^j$, at most one of its nodes is present in
the other subtrees.  Since $\Srcs$ and $\Snks$ are drawn at random and
have are of size at least $r/4$ and equal to $r$, respectively, it
follows from a standard Chernoff bound that each of these subtrees has
$\Omega(\log n)$ (resp., $\Theta(\log n)$), nodes from $\Srcs$ (resp.,
$\Snks$) whp.  In the remainder of the proof, we thus assume that the
preceding property holds for each of the graphs in the
$\Theta((n+k)\log n)$ levels of $\expandedG{\ell}$.

We now argue that every cut $C = (\Srcs, \Snks)$ of $\expandedG{\ell}$ has
capacity at least $rk$.  If any of the sources in $\Srcs$ is separated
from the super-source, then the capacity of the cut is at least $rk$
since the capacity of the edge connecting the super-source to any
source is $rk$.  So in the remainder, we assume that all nodes in $S$
are on the same side of the cut as the super-source.  Let $\Snks'$
denote the set of sinks that are separated from the super-source in
$C$; let $r' = |\Snks'|$.  All of the edges from $\Snks - \Snks'$ to
the super-sink cross $C$ and have a total capacity of $(r - r')k$.  It
thus remains to show that the total capacity of the edges crossing the
cut in the intermediate levels $1$ through $t$ is at least $r'k$.

Let $V_i$ denote the set of nodes in level $i$ that are in $\Srcs$.
Since every parallel edge has infinite capacity, we have $V_{i+1}
\supseteq V_i$.  Since each $V_i$ is of size at most $n$, there are at
least $t - n$ levels such that $V_{i+1} = V_i$.  For any such level
$i$, $C$ includes all edges that separate $\Srcs$ from $\Snks'$ in the
graph $G_i$.  By the property established above, there exist
edge-disjoint partition of a spanning tree of $G_i$ that such that
each tree in the partition contains $\Theta(\log n)$ nodes from both
$\Srcs$ and $\Snks$.  Therefore, for any arbitrary subset $\Snks'$ of
size $r'$, we can find $\Omega(r'/\log n)$ edges that separate
$\Snks'$ from $\Srcs$.  For the number of levels exceeding
$\Omega(k\log n)$, it then follows that the total capacity of the
edges crossing the cut in the intermediate levels is at least $r'k$.
This establishes the desired lower bound on the capacity of the cut,
completing the proof of the lemma.
\end{proof}

\tOfflineMultiport
\begin{proof}
By Lemma~\ref{lem:level.flow}, the gather step completes in $O(n + k)$
rounds.  We now argue that each phase completes in $O((n + k)\log n)$
rounds whp.  By Lemma~\ref{lem:sources}, the number of sources at the
start of phase $i$ is at least $2^{i-2}$ whp.  By
Lemmas~\ref{lem:maxflow} and~\ref{lem:double}, the number of rounds
needed for phase $i$ is $O((n + k)\log n)$ whp.  Since the number of
phases is $\lg n$, the statement of the theorem follows.
\end{proof}
\fi
